{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PageRank\n",
    "\n",
    "> PageRank 是网页排名的一种算法，也是google搜索的核心算法。属于图数据上的无监督学习方法。PageRank是有向图上的定义的一个随机游走模型，即一阶马尔科夫链，描述每一个节点在稳定状态下的概率，该概率就是每一个节点的PageRank值。\n",
    "\n",
    "这里定义一个简单的有向图的模型。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义每一个节点的转移矩阵\n",
    "M = torch.tensor([[0,   1/2, 1,  0],\n",
    "                  [1/3,  0,  0,  1/2],\n",
    "                  [1/3,  0,  0,  1/2],\n",
    "                  [1/3, 1/2, 0,  0],\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 由于是概率图，因此需要满足和为1的性质。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([1., 1., 1., 1.])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "torch.sum(M, dim=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def PageRank(R0, M, iters):\n",
    "    for _ in range(iters):\n",
    "        R0 = torch.matmul(M, R0)\n",
    "    return R0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[0.3333],\n",
       "        [0.2222],\n",
       "        [0.2222],\n",
       "        [0.2222]])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 开始的时候，设置每一个节点的概率一样。\n",
    "R0 = torch.ones((4,1)).fill_(1/4)\n",
    "PageRank(R0, M, 1000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 我们得到了每一个节点的稳定值."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PageRank的一般定义\n",
    "\n",
    "由于有些网页无法调到其他网页，因此基本的PageRank算法是不适用的。这里需要加上一个平滑项。\n",
    "\n",
    "$ R = dMR + \\frac{1-d}{n} 1$\n",
    "\n",
    "其中d为阻尼因子，$1$是分量为1的n维向量。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def PageRank(R0, d, M, iters):\n",
    "    dM = d * M\n",
    "    smooth = (1-d) * torch.ones((len(M),1)).fill_(1/len(M))\n",
    "    \n",
    "    for _ in range(iters):\n",
    "        R0 = torch.matmul(dM, R0) + smooth\n",
    "    return R0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[0.1014],\n",
       "        [0.1284],\n",
       "        [0.6419],\n",
       "        [0.1284]])"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M = torch.tensor([[0,   1/2, 0,  0],\n",
    "                  [1/3,  0,  0,  1/2],\n",
    "                  [1/3,  0,  1,  1/2],\n",
    "                  [1/3, 1/2, 0,  0],\n",
    "])\n",
    "\n",
    "R0 = torch.ones((4,1)).fill_(1/4)\n",
    "PageRank(R0, 0.8, M, 100000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 幂法来计算PageRank\n",
    "\n",
    "思想是使用特征值与特征向量计算。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = torch.tensor([[0,   0, 1],\n",
    "                  [1/2, 0, 0],\n",
    "                  [1/2, 1, 0],\n",
    "])\n",
    "\n",
    "x = torch.ones((3,1))\n",
    "\n",
    "A = 0.85 * M + (1-0.85) / 3 * torch.ones((3,3))\n",
    "\n",
    "# 这里采用的范数是无穷范数,即分量中绝对值的最大值。\n",
    "def get_norm(A):\n",
    "    A = torch.abs(A)\n",
    "    return torch.max(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "y = A @ x\n",
    "x = y / get_norm(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[0.9758],\n",
      "        [0.5405],\n",
      "        [1.0000]])\n"
     ]
    }
   ],
   "source": [
    "for _ in range(100):\n",
    "    t = x\n",
    "    y = A @ x\n",
    "    x = y / get_norm(y)\n",
    "    \n",
    "    if torch.norm(x-t, 2) < 0.0000001:\n",
    "        break\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[0.3878],\n",
      "        [0.2148],\n",
      "        [0.3974]])\n"
     ]
    }
   ],
   "source": [
    "print(x / torch.sum(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 逆矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = torch.tensor([[0,   0, 1],\n",
    "                  [1/2, 0, 0],\n",
    "                  [1/2, 1, 0],\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[0.3878],\n",
       "        [0.2148],\n",
       "        [0.3974]])"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "torch.inverse(torch.eye(3) - 0.85*M) @ ((1-0.85) / 3 * torch.ones((3,1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
